Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Курсова робота з дисципліни «Паралельні та розподілені обчислення» на тему: «Паралельне виконання операцій множення матриць» Номер залікової книжки: № 1009130 Завдання Розробити схему та описати процедуру перемноження матриці А (розмірністю N1*N2) на матрицю В (розмірністю N2*N3) на структурі з восьми процесорів. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму. Веремей Юрій Олегович n1=240 , n2=264, n3=е-149 – КІ-44 Таблиця 1. Часові параметри Співвідношення часових параметрів Пояснення  tu = 10* ts час виконання однієї операції множення  ts час виконання однієї операції сумування  tp = (10/4) ts час виконання однієї операції пересилання даних між процесорами  tz = (10/3) ts час виконання операції завантаження одних даних  tW= (10/4) ts час виконання операції вивантаження одних даних  3b-6b-2b-5b-10b-13b-14b-11b – КІ-44 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  В Е Р Е М Е Й Ю Р І Й О Л Е Г О В И Ч В Е Р   3 1  4 2    5 8  6 7           РЕЕМІЛЕЙ Буква Е дублюється тому беремо наступну вільну після неї Ю Буква Е знову дублюється тому беремо наступну після неї Г РЕЮМІЛГЙ Р = 93 = 01011101 Е = 171 = 10101011 Ю = 63 = 00111111 М = 43 = 00101011 І = 223 = 11011111 Л = 212 = 11010100 Г = 74 = 01001010 Й = 146 = 10010010  Таблиця 2. Матриця зв’язків між процесорами 1 2 3 4 5 6 7 8  1 0 1 0 1 1 1 0 1  2 1 0 1 0 1 0 1 1  3 0 0 0 1 1 1 1 1  4 0 0 1 0 1 0 1 1  5 1 1 0 1 0 1 1 1  6 1 1 0 1 0 0 0 0  7 0 1 0 0 1 0 0 0  8 1 0 0 1 0 0 1 0   Type = (
i)mod3 + 1 z = 1009130 (номер залікової книжки) Type=(1+0+0+9+1+3+0)mod3+1=3 Type = 3 розподілена пам’ять. tU = (Zk-3 +1)*tS = (Zk-2 +1)*tP = (Zk-1 +1)*tZ = (Zk+1)*tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки. Номер залікової книжки = 1009130 k=7 Tu=10*ts=2tp=4tz=1tw Анотація В даній курсовій роботі розроблено алгоритм паралельного множення двох матриць з розмірами 240х264 і 264х149. Початкові завантаження проводяться через розподілену пам’ять, тобто кожен з восьми процесорів має свою власну пам’ять і починає роботу з вже наперед поміщеними у неї підматрицями. Робота поділяється на такі етапи: проектування граф-схеми виконання алгоритму (побудова зв’язків між процесорами, кільця для обміну даними, граф-схема виконання алгоритму множення двох матриць з розподіленою пам'яттю); розробка функціональної схеми; розрахункова частина (розрахунок ефективності, часу виконання алгоритму, відсотка послідовної частини алгоритму тощо); програмна реалізація, яка включає в себе алгоритм роботи програми, його граф-схему та код програми. Програма написана на мові С++ з використанням технології MPI, оскільки вона найкраще підходить для вирішення даної задачі, і має консольний інтерфейс. Annotation In this course work was elaborated the algorithm of parallel multiplying tow matrices with dimensions 240х264 and 264х149. The initial load carried through distributed memory, that is, each of the eight processors has it’s own memory and starts with the already pre-placed in it’s submatrices. The work is divided into the following stages: designing graph-scheme of algorithm execution (construction bonds between processors, rings for data exchange, graph-scheme of execution the algorithm of multiplying two matrices with distributed memory); development of functional scheme; calculation part (calculation of efficiency, time of execution the algorithm, the percentage of sequential algorithm, etc); software implementation, which includes the algorithm of the program, it’s graph-schema and application code. The program is written in C++ using the technology of MPI, because it’s b...